In image processing, computer graphics and other physical sciences, distance maps are frequently used. In one type of distance map, the distance map gives a distance from every background pixel in an image to a nearest foreground or object pixel. In a binary image, the most common type of object pixel that is used for the distance determination is a boundary pixel on a surface of the object, A. Rosenfeld, J. Pfaltz, “Distance Functions in Digital Pictures”, Pattern Recognition, Vol 1, 1968, pp 33-61.
Distance maps have a central role in the comparison of binary images, particularly for images resulting from local features such as edge or corner detection. The distance map can also be used to obtain the medial axes of digital shapes.
There are various ways of generating distance maps, depending on which distance metric is used, and how local distance information is propagated. Distance metrics include the L1, L2, L∞, chamber transforms, see R. Haralick, L. Shapiro, “Computer and Robot Vision”, Vol. 1, Addison-Wesley Publishing Company, Chapter 5, 1992. The 2 (Euclidean) distance is the most common.
Chamfer metrics result in an approximation to the circular form, usually as an 8-sided or 16-sided closest fit polygon, G. Borgefors, “Hierarchical chamfer matching: A parametric edge matching algorithm”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(6):849865, 1988.
There are other distance metrics that aim to make the distance computation robust to noise. In a Gaussian distance map, the distance at a pixel is proportional to a weighted sum of distances of that pixel to all object pixels, with the weights inversely proportional to the distances. Gaussian functions are used as the weights. The summation has an averaging effect and reduces the effect of noise. As the standard deviation of the Gaussian function increases, the effect of noise decreases. However, averaging also reduces local details.
Because determining the exact Euclidean distance is computationally intensive, some methods use a mask, which is ‘swept’ over the image to determine approximations, such as the city-block, chess-board, or chamfer distances, see Rosenfeld et al.
One intuitive but extremely inefficient way of generating distance maps is to perform multiple successive morphological ‘erosion’ operations with a suitable structuring element until all foreground regions of the image have been eroded away. If each pixel is labeled with the number of erosions that have been performed before the pixel ‘disappears’, then this is just the distance map. The shape of the structuring element determines the type of the distance metric. A square element results in the chess-board distance transform, a cross shaped element yields the city-block distance transform, and a disc shaped element approximates the Euclidean distance transform.
The time complexity of those prior art methods is linear in the number of pixels of the image, but does not yield the exact Euclidean distance, which is required for some applications. Another drawback of those methods is that they are hard to perform in parallel because previously determined results need to be propagated during the computation.
A survey of efficient 2D morphological erosion methods that decompose the structuring element and take advantage of parallel rastering is described by F., R. Lotufo, “Classification of the Distance Transformation Algorithms under the Mathematical Morphology Approach,” XIII Brazilian Symposium on Computer Graphics and Image Processing, 2000.
A unified method that determines distance and a related nearest feature transform concurrently for arbitrary bit maps is described by D. Paglieroni, “A unified distance transform algorithm and architecture”, Journal Machine Vision and Applications Volume 5, Number 1, December, 1992. That method has an efficient implementation on serial processors based on parallel row followed by parallel column scanning.
A linear-time method for solving a class of minimization problems involving a cost function with both local and spatial terms is described by P. Felzenszwalb and D. Huttenlocher, “Distance Transforms of Sampled Functions,” Cornell Computing and Information Science, Technical Report, 2004. Those problems can be viewed as a generalization of classical distance transforms of binary images, where the binary image is replaced by an arbitrary sampled function.
Another recursive method requires column-wise half plane search followed by row-wise search to accelerate the Euclidean distance computation, Kolountzakis, K. Kutulakos, “Fast computation of the Euclidian distance maps for binary images,” Information Processing Letters, v. 43 n. 4, p. 181-184, Sep. 28, 1992.
Another method implements the chess-board distance on parallel processors, Y. H. Lee, S. J. Horng, “Optimal computing the chessboard distance transform on parallel processing systems,” Computer Vision and Image Understanding, v. 73 n. 3, p. 374-390, March 1999. That method was extended for Euclidean distance computation, Y. H. Lee, S. J. Horng, J. Seitzer, “Parallel Computation of the Euclidean Distance Transform on a Three-Dimensional Image Array,” IEEE Transactions on Parallel and Distributed Systems archive, 14:3, 203-212, March 2003. There, they derive geometry relations and properties among parallel planes, and adapt a parallel method on an emulated exclusive read exclusive write parallel random access machine (EREW PRAM).
An asymptotically optimal method for determining the Euclidean distances for a two-dimensional binary image is described by H. Breu, J. Gil, D. Kirkpatrick, M. Werman, “Linear Time Euclidean Distance Algorithms,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 5, pp. 529-533, May, 1995. Their method is based on the construction and regular sampling of a Voronoi diagram with sites including the unit pixels in the image. They construct the Voronoi diagram where the diagram intersects the horizontal lines passing through the centers of the pixels. Computationally, their method requires linear time. On the other hand, the explicit Voronoi diagram construction requires additional memory of a size proportional to the image.